/**
 * https://leetcode-cn.com/problems/assign-cookies/
 * 分发饼干
 * @param g 
 * @param s 
 */
const findContentChildren = (g: number[], s: number[]): number => {
    // 1. 对g和s进行排序
    g.sort((a, b) => a - b)
    s.sort((a, b) => a - b)

    // 2. 判断是否满足
    const len = s.length;
    let ans = 0,
        m = 0

    for (let i = 0; i < len; i++) {
        // 当前饼干满足
        if (s[i] >= g[m]) {
            ans++;
            m++
        }
    }

    return ans
};


const findContentChildren2 = (g: number[], s: number[]): number => {
    // 1. 将s映射成一个map, 存放饼干的数量
    const map: Record<number, number> = {}
    for (let sub of s) {
        map[sub] = map[sub] || 0
        map[sub]++
    }

    // 2 将g排序
    g.sort((a, b) => a - b)

    const keys: string[] = Object.keys(map).reverse(),
        len = keys.length;

    // 3. 从最小的饼干开始算
    let ans = 0;
    for (let sub of g) {
        // 刚刚有饼干合适
        if (map[sub] && map[sub] > 0) {
            ans++;
            map[sub]--
        } else {
            for (let i = len - 1; i >= 0; i--) {
                if (+keys[i] >= sub && map[+keys[i]] > 0) {
                    map[+keys[i]]--
                    ans++
                    // 直接结束
                    break;
                }
            }
        }
    }
    return ans
};

console.log(findContentChildren([10, 9, 8, 7], [5, 6, 7, 8]))